def extend_euclid(a,b):
    global x
    global y
    if(b==0):
        x=1
        y=0
        #print("d:{0} x:{1} y:{2}".format(a,x,y))
        return (a,x,y)
    else:
        d=extend_euclid(b,a%b)[0]
        tmp=x
        x=y
        y=tmp-(a/b)*y
        #print("d:{0} x:{1} y:{2}".format(d,x,y))
        return (d,x,y)

if __name__=='__main__':
    #ext_euclid(14,100)
    print(extend_euclid(14,100))
